package sword.chapter8Tree;

import java.util.Stack;

/**
 * 所有大于等于结点的值之和
 *
 * 方法1 O(n)
 * 颠倒的中序遍历，先遍历右树节点，最后遍历左树节点
 *
 * 方法2 O(2n)
 * 中序遍历，计算所有节点和total
 * 再次中序遍历，计算sum（不加当前节点值） cur.val = total - sum，然后 sum += cur.val
 *
 * @author K
 * @date 2021-12-12 17:46
 */
public class S54ConvertBST {
    public static TreeNode s54(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int sum = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            cur = stack.pop();
            sum+= cur.val;
            cur.val = sum;
            cur = cur.left;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node6;
        node2.left = node1;
        node2.right = node3;
        node6.left = node5;
        node6.right = node7;

        TreeNode result = s54(root);
        System.out.println();
    }
}
